// 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

// 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

//  

// 例如，给定三角形：

// [
//      [2],
//     [3,4],
//    [6,5,7],
//   [4,1,8,3]
// ]
// 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

//  

// 说明：

// 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 动态规划
// 时间复杂度：O(N^2)
// 空间复杂度：O(N^2)
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        dp[0][0] = triangle[0][0];
        for (int i{1}; i < n; ++i) {
            dp[i][0] = dp[i-1][0] + triangle[i][0];
            for (int j{1}; j < i; ++j) {
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];
        }
        return *min_element(dp[n-1].begin(), dp[n-1].end());
    }
};

// 动态规划+空间优化
// 时间复杂度：O(N^2)
// 空间复杂度：O(N)
// 为什么只有在递减地枚举 j 时，才能省去一个一维数组？当我们在计算位置 (i,j) 时，
// f[j+1] 到 f[i] 已经是第 i 行的值，而 f[0] 到 f[j] 仍然是第 i−1 行的值。此时我们直接通过
// f[j]=min(f[j−1],f[j])+c[i][j]进行转移，恰好就是在 (i−1,j−1) 和 (i−1,j) 中进行选择。
// 但如果我们递增地枚举 j，那么在计算位置 (i,j) 时，f[0] 到 f[j−1] 已经是第 i 行的值。
// 如果我们仍然使用上述状态转移方程，那么是在 (i,j−1) 和 (i−1,j) 中进行选择，就产生了错误。
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int>dp(n, 0);
        dp[0] = triangle[0][0];
        for (int i{1}; i < n; ++i) {
            dp[i] = dp[i-1] + triangle[i][i];
            for (int j{i -1}; j > 0; --j) { // 必须递减的来转移
                dp[j] = min(dp[j-1], dp[j]) + triangle[i][j];
            }
            dp[0] += triangle[i][0];
        }
        return *min_element(dp.begin(), dp.end());
    }
};

// 动态规划
// 从最底层往上
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.back());
        for(int i = triangle.size() - 2; i >= 0; i --)
            for(int j = 0; j <= i; j ++)
                dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
        return dp[0];
    }
};



int main() {

    Solution s;
    vector<vector<int>> v{{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
    s.minimumTotal(v);
    return 0;
}